package com.bo.day20231123;

/**
 * 区间和的个数：https://leetcode.cn/problems/count-of-range-sum/
 * 给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数
 * 输入：nums = [-2,5,-1], lower = -2, upper = 2
 * 输出：3
 * 解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2
 * 解题思路：
 * nums={-2,5,-1} [-2,2]
 * 前缀和数组 sum={-2,3,2}
 * 前缀和数组计算
 * sum(i,j)=sum(0~j)-(0~i-1)
 * 比如 i=1,j=2
 * sum(1,2)=sum(0~2)-(0~1-1)=2-(-2)=4等于arr[1]+arr[2]=5+-1=4
 * 计算
 * 0-0(-2) 1-1 (5)   2-2(-1)
 * 0-1 (-3)  1-2(-4)
 * 0-2 (2)
 * ---------------------------------
 * 0结尾的1个
 * 1结尾的0个
 * 2结尾的2个
 * 输出3
 * 求出i结尾的前缀和满足[lower,upper],怎么取求呢？
 * 假设0-i,整体得累加和是x,题目[lower,upper]
 * 求出必须以i位置结尾得子数组目标有多个在[lower,upper]范围上
 * 等同于,取求i之前得所以算有前缀和中有多少个前缀和在[x-lower,x-upper]上
 * 比如说 0-17 的前缀和为100,[10,40]
 * 情况1) 0-0的前缀和为0,1-17的前缀和=(0-17)前缀和-(0-0)前缀和=100-0=100,100不满足在[10,40]
 * 情况2) 0-1的前缀和为50,2-17的前缀和=(0-17)前缀和-(0-1)前缀和=100-50=50,50不满足在[10,40]
 * 情况3) 0-2的前缀和为60,3-17的前缀和=(0-17)前缀和-(0-3)前缀和=100-60=40,40满足在[10,40]
 * 情况4) 0-3的前缀和为70,4-17的前缀和=(0-17)前缀和-(0-4)前缀和=100-70=30,30满足在[10,40]
 * 由此可以推出 求出必须以i位置结尾得子数组目标有多个在[lower,upper]范围上,等同于,取求i之前得所以算有前缀和中有多少个前缀和在[x-lower,x-upper]范围是
 * 前缀和左数组中的数必须要在[x-lower,x-upper]的范围上,左数组中的数不能大于x-lower,不能小于x-upper
 * nums={-2,5,-1} [-2,2]
 * sum ={-2,3,2}
 * i=2,的前缀等于2
 * 0-2 的前缀和为2
 *
 * @Author: gpb
 * @Date: 2023/11/28 15:02
 * @Description:
 */
public class CountRangeSum {
    public static void main (String[] args) {
        int[] nums = {-2, 5, -1};
        System.out.println(countRangeSum(nums, -2, 2));
        int[] arr = {-1, 3, 2, 0, 5, -3};
        System.out.println(countRangeSum(arr, 2, 7));

    }

    public static int countRangeSum (int[] nums, int lower, int upper) {
        if (nums == null) {
            return 0;
        }
        // 前缀和
        int[] sum = new int[nums.length];
        sum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sum[i] = sum[i - 1] + nums[i];
        }
        return process(sum, 0, sum.length - 1, lower, upper);
    }

    public static int process (int[] arr, int l, int r, int lower, int upper) {
        if (l == r) {
            // 如果l位置和r位置相等,来到一个位置的子数组,需要判断这一个位置的子数组是否符合lower和upper
            // 符合返回1,不符合返回0
            if (arr[l] >= lower && arr[l] <= upper) {
                return 1;
            }
            return 0;
        }
        // 中点位置
        int mid = l + ((r - l) >> 1);
        return process(arr, l, mid, lower, upper) + process(arr, mid + 1, r, lower, upper) + merge(arr, l, mid, r, lower, upper);
    }

    public static int merge (int[] arr, int l, int mid, int r, int lower, int upper) {
        int ans = 0;
        int ansPL = l;
        int ansPR = l;
        /*
         * 遍历右数组
         * */
        for (int i = mid + 1; i <= r; i++) {
            // 最大上线
            int max = arr[i] - lower;
            // 最大下线
            int min = arr[i] - upper;
            // 左数组范围条件
            // 滑动的左数组中的指针,不能小于最大下线
            while (ansPL <= mid && arr[ansPL] < min) {
                // 如果小于最大下线,就继续++
                ansPL++;
            }
            // 移动到最大上线最后一个位置
            while (ansPR <= mid && arr[ansPR] <= max) {
                ansPR++;
            }
            //r-l 说明这个区域的数到i位置得数组符合在[lower,upper]
            ans += ansPR - ansPL;
        }
        // 排序
        int[] help = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= r) {
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
        return ans;
    }
}
